//https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/submissions/589245680/
class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        vector<vector<int>> dirs = { {1,0},{-1,0},{0,1},{0,-1} };
        int m = maze.size(), n = maze[0].size();
        queue<pair<int, int>> q;
        q.emplace(entrance[0], entrance[1]);
        maze[entrance[0]][entrance[1]] = '-';
        int d = 0;
        while (!q.empty()) {
            int sz = q.size();

            for (int k = 0; k < sz; k++) {
                auto [x, y] = q.front(); q.pop();
                for (auto& dir : dirs) {
                    int xx = x + dir[0], yy = y + dir[1];
                    if (xx >= 0 && xx < m && yy >= 0 && yy < n) {
                        if (maze[xx][yy] == '.') {
                            q.emplace(xx, yy);
                            maze[xx][yy] = '-';
                        }
                    }
                    else if (x != entrance[0] || y != entrance[1]) {
                        return d;
                    }
                }
            }
            d++;
        }
        return -1;
    }
};